package org.sky.algorithm.sort;

import java.util.Arrays;

/**
 * 快速排序
 *
 * @author fog
 * @date 2021/10/30
 */

public class Quick {

    public static void main(String[] args) {

        int[] arrList = new int[]{2, 5, 3, 4, 9, 0, 6, 7, 1, 8};

        System.out.println("未排序数据：\n  " + Arrays.toString(arrList));

        quickSort(arrList, 0, arrList.length - 1);

        System.out.println("快速排序后数据：\n  " + Arrays.toString(arrList));


    }

    public static void quickSort(int[] arrList, int start, int end) {

        if (start < end) {

            // 把数组中第一位数为标准数
            int standard = arrList[start];

            // 记录需要排序的下标
            int small = start, big = end;

            // 循环找比标准数大的数和比标准数小的数
            while (small < big) {
                // 右边的数比标准数大
                while (small < big && standard <= arrList[big]) {
                    big--;
                }

                // 使用右边的数字替换左边的数字
                arrList[small] = arrList[big];

                // 如果左边的数字大于右边的数字
                while (small < big && arrList[small] <= standard) {
                    small++;
                }

                arrList[big] = arrList[small];

            }

            // 把标准书赋给小于所在位置的元素
            arrList[small] = standard;

            // 处理所有小的数
            quickSort(arrList, start, small);

            // 处理所有大的数
            quickSort(arrList, small + 1, end);

        }

    }

}
